package binPack.guillotine
{
	import binPack.Config;
	import binPack.DisjointRectCollection;
	import binPack.RectSize;
	
	import flash.geom.Rectangle;

	/**
	 * Implements different bin packer algorithms that use the GUILLOTINE data structure.
	 * This work is released to Public Domain, do whatever you want with it.
	 * @see https://github.com/juj/RectangleBinPack/blob/master/GuillotineBinPack.cpp
	 * @author Jukka Jylänki
	 * @revised adodo08
	 * @date  2016/06/23
	 *
	 */
	public class GuillotineBinPack
	{
		private var binWidth:int;
		private var binHeight:int;
		private var disjointRects:DisjointRectCollection;
		
		/// Stores a list of all the rectangles that we have packed so far. This is used only to compute the Occupancy ratio,
		/// so if you want to have the packer consume less memory, this can be removed.
		private var usedRectangles:Vector.<Rectangle>;
		
		/// Stores a list of rectangles that represents the free area of the bin. This rectangles in this list are disjoint.
		private var freeRectangles:Vector.<Rectangle>;
		/**
		 *  Initializes a new bin of the given size.
		 * */
		public function GuillotineBinPack(width:int=0, height:int=0)
		{
			Init(width, height);
		}
		/**
		 * (Re)initializes the packer to an empty bin of width x height units. Call whenever
		 *  you need to restart with a new bin.
		 * */
		public function Init(width:int, height:int):void{
			this.binHeight = height;
			this.binWidth = width;
			this.usedRectangles = new Vector.<Rectangle>();
			this.freeRectangles = new Vector.<Rectangle>();
			var rect:Rectangle = new Rectangle(0,0,width, height);
			this.freeRectangles.push(rect);
			if( Config.DEBUG ){
				disjointRects = new DisjointRectCollection();
			}
		}
		/**
		 * Inserts a single rectangle into the bin. The packer might rotate the rectangle, in which case the returned
		 * struct will have the width and height values swapped.
		 * @param width
		 * @param height
		 * @param merge	If true, performs free Rectangle Merge procedure after packing the new rectangle. This procedure
		 * tries to defragment the list of disjoint free rectangles to improve packing performance, but also takes up 
		 * some extra time.
		 * @param rectChoice The free rectangle choice heuristic rule to use.
		 * @param splitMethod	The free rectangle split heuristic rule to use.
		 * @return 
		 * 
		 */		
		public function Insert(width:int, height:int, merge:Boolean, rectChoice:int=0, splitMethod:int=0):Rectangle{
			// Find where to put the new rectangle.
			var freeNodeIndex:int = 0;
			var result:* = FindPositionForNewNode(width, height, rectChoice, freeNodeIndex);
			var newRect:Rectangle = result.node;
			freeNodeIndex = result.index;
			
			// Abort if we didn't have enough space in the bin.
			if (newRect.height == 0)
				return newRect;
			
			// Remove the space that was just consumed by the new rectangle.
			SplitFreeRectByHeuristic(freeRectangles[freeNodeIndex], newRect, splitMethod);
			freeRectangles.splice(freeNodeIndex,1);
			
			// Perform a Rectangle Merge step if desired.
			if (merge)
				MergeFreeList();
			
			// Remember the new used rectangle.
			usedRectangles.push(newRect);
			
			// Check that we're really producing correct packings here.
			if( Config.DEBUG)
				trace(disjointRects.Add(newRect) == true);
			
			return newRect;
		}
		
		/**
		 * Inserts a list of rectangles into the bin. 
		 * @param rects	The list of rectangles to add. This list will be destroyed in the packing process.
		 * @param merge	If true, performs Rectangle Merge operations during the packing process.
		 * @param rectChoice	The free rectangle choice heuristic rule to use.
		 * @param splitMethod	The free rectangle split heuristic rule to use.
		 * 
		 */		
		public function InsertRects( rects:Vector.<RectSize>, merge:Boolean, rectChoice:int, splitMethod:int):void{
			// Remember variables about the best packing choice we have made so far during the iteration process.
			var bestFreeRect:int = 0;
			var bestRect:int = 0;
			var bestFlipped:Boolean = false;
			
			// Pack rectangles one at a time until we have cleared the rects array of all rectangles.
			// rects will get destroyed in the process.
			while(rects.length > 0)
			{
				// Stores the penalty score of the best rectangle placement - bigger=worse, smaller=better.
				var bestScore:int = int.MAX_VALUE;
				
				for(var i:int = 0; i < freeRectangles.length; ++i)
				{
					for(var j:int = 0; j < rects.length; ++j)
					{
						// If this rectangle is a perfect match, we pick it instantly.
						if (rects[j].width == freeRectangles[i].width && rects[j].height == freeRectangles[i].height)
						{
							bestFreeRect = i;
							bestRect = j;
							bestFlipped = false;
							bestScore = int.MIN_VALUE;
							i = freeRectangles.length; // Force a jump out of the outer loop as well - we got an instant fit.
							break;
						}
							// If flipping this rectangle is a perfect match, pick that then.
						else if (rects[j].height == freeRectangles[i].width && rects[j].width == freeRectangles[i].height)
						{
							bestFreeRect = i;
							bestRect = j;
							bestFlipped = true;
							bestScore = int.MIN_VALUE;
							i = freeRectangles.length; // Force a jump out of the outer loop as well - we got an instant fit.
							break;
						}
							// Try if we can fit the rectangle upright.
						else if (rects[j].width <= freeRectangles[i].width && rects[j].height <= freeRectangles[i].height)
						{
							var score:int = ScoreByHeuristic(rects[j].width, rects[j].height, freeRectangles[i], rectChoice);
							if (score < bestScore)
							{
								bestFreeRect = i;
								bestRect = j;
								bestFlipped = false;
								bestScore = score;
							}
						}
							// If not, then perhaps flipping sideways will make it fit?
						else if (rects[j].height <= freeRectangles[i].width && rects[j].width <= freeRectangles[i].height)
						{
							score = ScoreByHeuristic(rects[j].height, rects[j].width, freeRectangles[i], rectChoice);
							if (score < bestScore)
							{
								bestFreeRect = i;
								bestRect = j;
								bestFlipped = true;
								bestScore = score;
							}
						}
					}
				}
				
				// If we didn't manage to find any rectangle to pack, abort.
				if (bestScore == int.MAX_VALUE)
					return;
				
				// Otherwise, we're good to go and do the actual packing.
				var newNode:Rectangle;
				newNode.x = freeRectangles[bestFreeRect].x;
				newNode.y = freeRectangles[bestFreeRect].y;
				newNode.width = rects[bestRect].width;
				newNode.height = rects[bestRect].height;
				
				if (bestFlipped){
//					std::swap(newNode.width, newNode.height);
					var t:int = newNode.width;
					newNode.width = newNode.height;
					newNode.height = t;
				}
					
				
				// Remove the free space we lost in the bin.
				SplitFreeRectByHeuristic(freeRectangles[bestFreeRect], newNode, splitMethod);
				freeRectangles.splice(bestFreeRect,1);
				
				// Remove the rectangle we just packed from the input list.
				rects.splice(bestRect,1);
				
				// Perform a Rectangle Merge step if desired.
				if (merge)
					MergeFreeList();
				
				// Remember the new used rectangle.
				usedRectangles.push(newNode);
				
				// Check that we're really producing correct packings here.
//				debug_assert(disjointRects.Add(newNode) == true);
			}
		}
		
		/// @return True if r fits inside freeRect (possibly rotated).
		public function Fits(r:RectSize, freeRect:Rectangle):Boolean
		{
			return (r.width <= freeRect.width && r.height <= freeRect.height) ||
				(r.height <= freeRect.width && r.width <= freeRect.height);
		}
		
		/// @return True if r fits perfectly inside freeRect, i.e. the leftover area is 0.
		public function  FitsPerfectly(r:RectSize, freeRect:Rectangle):Boolean
		{
			return (r.width == freeRect.width && r.height == freeRect.height) ||
				(r.height == freeRect.width && r.width == freeRect.height);
		}
		
		/** Implements GUILLOTINE-MAXFITTING, an experimental heuristic that's really cool but didn't quite work in practice.
		*	void InsertMaxFitting(std::vector<RectSize> &rects, std::vector<Rect> &dst, bool merge, 
		*		FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod);
		*
		* Computes the ratio of used/total surface area. 0.00 means no space is yet used, 1.00 means the whole bin is used.
		 * */
		public function Occupancy():Number{
			///\todo The occupancy rate could be cached/tracked incrementally instead
			///      of looping through the list of packed rectangles here.
			var usedSurfaceArea:Number = 0;
			for(var i:int = 0; i < usedRectangles.length; ++i)
				usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
			
			return usedSurfaceArea / (binWidth * binHeight);
		}
		
		/// Returns the internal list of disjoint rectangles that track the free area of the bin. You may alter this vector
		/// any way desired, as long as the end result still is a list of disjoint rectangles.
		public function GetFreeRectangles():Vector.<Rectangle> { return freeRectangles; }
		
		/// Returns the list of packed rectangles. You may alter this vector at will, for example, you can move a Rect from
		/// this list to the Free Rectangles list to free up space on-the-fly, but notice that this causes fragmentation.
		public function  GetUsedRectangles():Vector.<Rectangle> { return usedRectangles; }
		
		/// Performs a Rectangle Merge operation. This procedure looks for adjacent free rectangles and merges them if they
		/// can be represented with a single rectangle. Takes up Theta(|freeRectangles|^2) time.
		public function MergeFreeList():void{
			if( Config.DEBUG ){
				var testCol:DisjointRectCollection = new DisjointRectCollection();
				for(var i:int = 0; i < freeRectangles.length; ++i){
					trace(testCol.Add(freeRectangles[i]) == true);
				}
			}
			for(var i:int = 0; i < freeRectangles.length; ++i)
				for(var j:int = i+1; j < freeRectangles.length; ++j)
				{
					if (freeRectangles[i].width == freeRectangles[j].width && freeRectangles[i].x == freeRectangles[j].x)
					{
						if (freeRectangles[i].y == freeRectangles[j].y + freeRectangles[j].height)
						{
							freeRectangles[i].y -= freeRectangles[j].height;
							freeRectangles[i].height += freeRectangles[j].height;
							freeRectangles.splice( j, 1);
							--j;
						}
						else if (freeRectangles[i].y + freeRectangles[i].height == freeRectangles[j].y)
						{
							freeRectangles[i].height += freeRectangles[j].height;
							freeRectangles.splice( j,1);
							--j;
						}
					}
					else if (freeRectangles[i].height == freeRectangles[j].height && freeRectangles[i].y == freeRectangles[j].y)
					{
						if (freeRectangles[i].x == freeRectangles[j].x + freeRectangles[j].width)
						{
							freeRectangles[i].x -= freeRectangles[j].width;
							freeRectangles[i].width += freeRectangles[j].width;
							freeRectangles.splice( j, 1);
							--j;
						}
						else if (freeRectangles[i].x + freeRectangles[i].width == freeRectangles[j].x)
						{
							freeRectangles[i].width += freeRectangles[j].width;
							freeRectangles.splice(j, 1);
							--j;
						}
					}
				}
			
			if( Config.DEBUG ){
				testCol.Clear();
				for(var i:int = 0; i < freeRectangles.length; ++i){
					trace(testCol.Add(freeRectangles[i]) == true);
				}
			}
			
		}
		
		/// Returns the heuristic score value for placing a rectangle of size width*height into freeRect. Does not try to rotate.
		public function ScoreByHeuristic( width:int, height:int, freeRect:Rectangle,  rectChoice:int):int
		{
			switch(rectChoice)
			{
				case FreeRectChoiceHeuristic.RectBestAreaFit: 
					return ScoreBestAreaFit(width, height, freeRect);
				case FreeRectChoiceHeuristic.RectBestShortSideFit: 
					return ScoreBestShortSideFit(width, height, freeRect);
				case FreeRectChoiceHeuristic.RectBestLongSideFit: 
					return ScoreBestLongSideFit(width, height, freeRect);
				case FreeRectChoiceHeuristic.RectWorstAreaFit: 
					return ScoreWorstAreaFit(width, height, freeRect);
				case FreeRectChoiceHeuristic.RectWorstShortSideFit: 
					return ScoreWorstShortSideFit(width, height, freeRect);
				case FreeRectChoiceHeuristic.RectWorstLongSideFit: 
					return ScoreWorstLongSideFit(width, height, freeRect);
				default: 
					return int.MAX_VALUE;
			}

		}
		
		private function ScoreWorstAreaFit(width:int, height:int, freeRect:Rectangle):int
		{
			return -ScoreBestAreaFit(width, height, freeRect);
		}
		
		private function ScoreBestLongSideFit(width:int, height:int, freeRect:Rectangle):int
		{
			var leftoverHoriz:int = Math.abs(freeRect.width - width);
			var leftoverVert:int = Math.abs(freeRect.height - height);
			var leftover:int = Math.max(leftoverHoriz, leftoverVert);
			return leftover;
		}
		private function ScoreBestShortSideFit(width:int, height:int, freeRect:Rectangle):int
		{
			var leftoverHoriz:int = Math.abs(freeRect.width - width);
			var leftoverVert:int = Math.abs(freeRect.height - height);
			var leftover:int = Math.min(leftoverHoriz, leftoverVert);
			return leftover;
		}
		
		private function ScoreBestAreaFit(width:int, height:int, freeRect:Rectangle):int
		{
			return freeRect.width * freeRect.height - width * height;
		}
		
		private function ScoreWorstShortSideFit(width:int, height:int, freeRect:Rectangle):int
		{
			return -ScoreBestShortSideFit(width, height, freeRect);
		}
		
		private function ScoreWorstLongSideFit(width:int, height:int, freeRect:Rectangle):int
		{
			return -ScoreBestLongSideFit(width, height, freeRect);
		}
		
		public function FindPositionForNewNode(width:int, height:int, rectChoice:int, nodeIndex:int):Object
		{
			var bestNode:Rectangle = new Rectangle();
			
			var bestScore:int = int.MAX_VALUE;
			
			/// Try each free rectangle to find the best one for placement.
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				// If this is a perfect fit upright, choose it immediately.
				if (width == freeRectangles[i].width && height == freeRectangles[i].height)
				{
					bestNode.x = freeRectangles[i].x;
					bestNode.y = freeRectangles[i].y;
					bestNode.width = width;
					bestNode.height = height;
					bestScore = int.MIN_VALUE;
					nodeIndex = i;
					if( Config.DEBUG)
						disjointRects.Disjoint(bestNode);
					break;
				}
				// If this is a perfect fit sideways, choose it.
				else if (height == freeRectangles[i].width && width == freeRectangles[i].height)
				{
					bestNode.x = freeRectangles[i].x;
					bestNode.y = freeRectangles[i].y;
					bestNode.width = height;
					bestNode.height = width;
					bestScore =int.MIN_VALUE;
					nodeIndex = i;
					if( Config.DEBUG)
						disjointRects.Disjoint(bestNode);
					break;
				}
					// Does the rectangle fit upright?
				else if (width <= freeRectangles[i].width && height <= freeRectangles[i].height)
				{
					var score:int = ScoreByHeuristic(width, height, freeRectangles[i], rectChoice);
					
					if (score < bestScore)
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestScore = score;
						nodeIndex = i;
						if( Config.DEBUG)
							disjointRects.Disjoint(bestNode);
					}
				}
					// Does the rectangle fit sideways?
				else if (height <= freeRectangles[i].width && width <= freeRectangles[i].height)
				{
					var score:int = ScoreByHeuristic(height, width, freeRectangles[i], rectChoice);
					
					if (score < bestScore)
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestScore = score;
						nodeIndex = i;
						if( Config.DEBUG)
							disjointRects.Disjoint(bestNode);
					}
				}
			}
			return {node:bestNode, index:nodeIndex};
		}
		
		private function SplitFreeRectByHeuristic(freeRect:Rectangle, placedRect:Rectangle, method:int):void
		{
			// Compute the lengths of the leftover area.
			const w:int = freeRect.width - placedRect.width;
			const h:int = freeRect.height - placedRect.height;
			
			// Placing placedRect into freeRect results in an L-shaped free area, which must be split into
			// two disjoint rectangles. This can be achieved with by splitting the L-shape using a single line.
			// We have two choices: horizontal or vertical.	
			
			// Use the given heuristic to decide which choice to make.
			
			var splitHorizontal:Boolean;
			switch(method)
			{
				case GuillotineSplitHeuristic.SplitShorterLeftoverAxis:
					// Split along the shorter leftover axis.
					splitHorizontal = (w <= h);
					break;
				case GuillotineSplitHeuristic.SplitLongerLeftoverAxis:
					// Split along the longer leftover axis.
					splitHorizontal = (w > h);
					break;
				case GuillotineSplitHeuristic.SplitMinimizeArea:
					// Maximize the larger area == minimize the smaller area.
					// Tries to make the single bigger rectangle.
					splitHorizontal = (placedRect.width * h > w * placedRect.height);
					break;
				case GuillotineSplitHeuristic.SplitMaximizeArea:
					// Maximize the smaller area == minimize the larger area.
					// Tries to make the rectangles more even-sized.
					splitHorizontal = (placedRect.width * h <= w * placedRect.height);
					break;
				case GuillotineSplitHeuristic.SplitShorterAxis:
					// Split along the shorter total axis.
					splitHorizontal = (freeRect.width <= freeRect.height);
					break;
				case GuillotineSplitHeuristic.SplitLongerAxis:
					// Split along the longer total axis.
					splitHorizontal = (freeRect.width > freeRect.height);
					break;
				default:
					splitHorizontal = true;
			}
			
			// Perform the actual split.
			SplitFreeRectAlongAxis(freeRect, placedRect, splitHorizontal);
		}
		/// This function will add the two generated rectangles into the freeRectangles array. The caller is expected to
		/// remove the original rectangle from the freeRectangles array after that.
		private function SplitFreeRectAlongAxis(freeRect:Rectangle, placedRect:Rectangle, splitHorizontal:Boolean):void
		{
			// Form the two new rectangles.
			var bottom:Rectangle = new Rectangle();
			bottom.x = freeRect.x;
			bottom.y = freeRect.y + placedRect.height;
			bottom.height = freeRect.height - placedRect.height;
			
			var right:Rectangle = new Rectangle();
			right.x = freeRect.x + placedRect.width;
			right.y = freeRect.y;
			right.width = freeRect.width - placedRect.width;
			
			if (splitHorizontal)
			{
				bottom.width = freeRect.width;
				right.height = placedRect.height;
			}
			else // Split vertically
			{
				bottom.width = placedRect.width;
				right.height = freeRect.height;
			}
			
			// Add the new rectangles into the free rectangle pool if they weren't degenerate.
			if (bottom.width > 0 && bottom.height > 0)
				freeRectangles.push(bottom);
			if (right.width > 0 && right.height > 0)
				freeRectangles.push(right);
			if(Config.DEBUG){
				disjointRects.Disjoint(bottom);
				disjointRects.Disjoint(right);
			}
		}

	}
}